package com.hdu.other.dp.three;

public class lc879 {
    class Solution {

        final int p = 1000000007;
        public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
            int[][][] dp = new int[group.length + 1][minProfit + 1][n + 1];
            for (int i = 0; i < group.length + 1; i++)
                for (int j = 0; j < minProfit + 1; j++)
                    for (int k = 0; k < n + 1; k++)
                        dp[i][j][k] = -1;
            return f(n, minProfit, group, profit, 0, dp);
        }

        int f(int n, int minProfit, int[] group, int[] profit, int index, int[][][] dp)
        {
            if (index == group.length)
            {
                return minProfit <= 0 ? 1 : 0;
            }

            if (n <= 0)
            {
                return minProfit <= 0 ? 1 : 0;
            }
            if (dp[index][minProfit][n] != -1)
            {
                return dp[index][minProfit][n];
            }
            int res;
            res = f(n, minProfit, group, profit, index + 1, dp);
            if (n >= group[index])
            {
                res = (res + f(n - group[index], Math.max(minProfit - profit[index], 0), group, profit, index + 1, dp)) % p;
            }
            return dp[index][minProfit][n] = res;
        }
    }
}
